package cn.itcast.algorithm;

/**
 * 题目：
 *  如果对于一个字符串A，将A的前面任意一部分挪到后边去形成的字符串称为A的旋转词。
 *  比如A=”12345”,A的旋转词有”12345”,”23451”,”34512”,”45123”和”51234”。
 *  对于两个字符串A和B，请判断A和B是否互为旋转词。
 *  给定两个字符串A和B及他们的长度lena，lenb，请返回一个bool值，代表他们是否互为旋转词。
 *
 * 举例：
 * a = “ cdab “ , b = “ abcd “ 。返回 true。
 * a = “ 1ab2 “ , b = “ ab12 “ 。返回 false。
 * a = “ 2ab1 “ , b= “ ab12 “ 。 返回 true。
 *
 * 测试样例：
 *  “cdab”,4,”abcd”,4
 *  返回：true
 *
 *  思路：
 *  最优解时间复杂度为 O(N)
 *  先判断字符串 a 和 b 是否长度相等。
 *  如果长度相等，生成 a + a 的大字符串。
 *  然后判断大字符串中是否包含 b 字符串。（使用 kmp 算法判断）如果大字符串中包含字符串 b ，那么字符串 a 和 b 就互为旋转词。
 *  举例：
 *  a = “ 1234 “
 *  a + a = “ 12341234 “
 *  很明显发现，如果字符串 a 的长度为 N，在 a + a 的大字符串中，任意一个长度为 N 的子串都是 a 的旋转词
 * create by zhangtian3 on 2019/4/9
 */
public class Rotation {
    public static boolean chkRotation(String A, int lena, String B, int lenb) {
        // write code here
        if (lena != lenb){
            return false;
        }else {
            String str = A + A;
            return str.contains(B);
        }
    }

    /**
     * 也可以使用 indexOf。
     * 其区别是：
     * contains 是找指定字符串是否包含一个字符串，返回值的 boolean 类型，即只有 true 和 false
     * indexOf 有多个重载，但无论哪个，都是做一定的匹配，然后把匹配的第一个字符的位置返回，返回的是 int 类型，如果没找到，那么返回 -1
     * 稍微再深究一下的我看了下 contains 的源码，结果发现他调用的是  indexOf 方法
     * @param args
     */
    public static void main(String[] args) {
        System.out.println(Rotation.chkRotation("1234", 4, "2341", 4));
    }
}
